/*
    a[0 ~ mid]为已经排好序的
    a[mid+1 ~ N]也是已经排好序的。
    要归并到一个有序的a[0 ~ N]中
*/
#include <iostream>

//空间复杂度O（1）
//时间复杂度:比较次数最好是1，最坏是mid次 ，移动次数最好是0次，最坏是mid ，这样看来是O(n^2)时间复杂度
int merge(int a[], int len, int mid)
{
    int temp;
    int i=0;
    int j=mid+1;
    int k;

    if (len < 1 || mid<0 || mid>len-1)
    {
        return 0;   //ERROR
    }

    while(j<=len-1)
    {
        while(a[i]<=a[j])
        {
            i++;
        }
        if (i>=j)
        {
            return 1;
        } else
        {
            k=j;
            temp = a[j];
            while (k>i)
            {
                a[k] = a[k-1];
                k--;
            }
            a[k] = temp;
        }
        i++;    //i++似乎不要也可以,
        j++;
    }
    return 1;
}

int main()
{
    int a[10] = {1,2,3,7,11,12, 7,8,9,10};
    int mid= 5; //mid是下标，从0开始计的
    merge(a, sizeof(a)/sizeof(int), mid);
    for (int i=0; i<sizeof(a)/sizeof(int) ; i++)
    {
        std::cout<<a[i]<<", ";
    }
}
